Lenore Blum's Home Page

Lenore Blum
Distinguished Career Professor of Computer Science *
PhD (M.I.T.)

Presidential Award

More Photos

CS4HS slide show (15mb)

Photos by: Glenn Brookes

“An Outreach Program for HS CS teachers” (L. Blum, T.Cortina)

Expanding Your Horizons

What we were doing in the 70’s

“The Math Science Connection:

Educating Women for Today” (Flash-36mb), (Flash-10mb), (mpg version - 155mb)

Math/Science Network 30^th Anniversary Celebration

The Movie!

Professor Lenore Blum

Department of Computer Science

School of Computer Science

Carnegie Mellon University

Pittsburgh, PA 15213-3891

Office: Gates 7105

Phone: (412) 268-8139

Fax: (412) 268-5576

lblum@cs.cmu.edu

Executive Assistant:

Cleah Schlueter

Office: Gates 4113

Phone: (412) 268-9656
Mobile:(412) 728-2854

cleah@cs.cmu.edu

Project Olympus

NUMB3RS

Blum Family in the News

(and back in the 60’s)

Photos by: Darrell Sapp

Pittsburgh Post-Gazette

FLAC (15-453)

Women@SCSwweb site

“Culture and Computing”

“Similarity is the Difference”

“The Evolving Culture of Computing”

Full version (25 pp); Shorter Version (17 pp)

“Building an Effective CS Student Organizaation: The Carnegie Mellon Women@SCS Action Plan”

“Diversifying the Images of CS” (C. Frieze, E. Treat)

“Transforming the Culture of Computing”

“Women in Computer Science: The Carnegie Mellon Experience” (2.5mb)

“Women in Computer Science: The Carnegie Mellon Experience” (GraceHopper 2000 Proposal)

“From Bits to Bots” (GraceHopper 2002 Proposal )

Women@IT: Graduate Education, The Next Big Thing (GraceHopper 2004 Proposal)

Computer Science Outreach Poster (10mb) (1mb)

Outreach Brochures

Outreach Roadshows

*I am also:

Founding Director, Project Olympus.

Co-Director (with Guy Blelloch) of the NSF-ITR ALADDIN Center.

Faculty Advisor for Women@SCS.
Carol Frieze is Women@SCS Director/Program Coordinator. Women@SCS-Inquiries

Faculty Advisor for the SCS Web Site.
Carol Frieze is SCS Web Team Supervisor/Coordinator.

TOP

Research Conferences Publications Biography Family ShortVita Images

Research

Complexity and Real Computation.

In 1989, Steve Smale, Mike Shub and I introduced a theory of computation and complexity over an arbitrary ring or field R. In 1997, along with Felipe Cucker, we published a book, Complexity and Real Computation (Springer-Verlag). From our Introduction:

“The classical theory of computation had its origin in the work of logicians -- of Gödel, Turing, ... , among others -- in the 1930’s. The model of computation developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science.

“The point of view of this book is that the Turing model (we call it “classical”) with it's dependence on 0’s and 1’s, is fundamentally inadequate for giving such a foundation for modern scientific computation, where most of the algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms.”

Our approach applies to the analysis of algorithms over continuous domains as well as the discrete. The classical theory is recovered if we allow the ring R to be Z₂(the integers mod 2). But now R can also be the real or complex numbers, or any other field. The familiar complexity classes P, NP and fundamental question “does P = NP?” make sense over R and moreover, relate explicitly to fundamental problems in mathematics such as Hilbert’s Nullstellensatz. Thus, we are particularly interested in research concerning the complexity of algorithms that solve systems of polynomial equations.

Transfer Principles for Complexity Theory. A powerful tool of the classical theory is that of reduction: If problem A can be shown to be reducible to problem B, then techniques for solving B can be used to solve A. Classically, A and B are both discrete, i.e. defined over the same domain Z₂. But now we have an additional powerful tool, namely that of transfer:

When there was essentially only one model of computation (i.e. over Z₂), it didn't make sense to transfer complexity results from one domain to another. But now, transfer becomes a real possibility. We can ask: Suppose we can show P = NP over the complex numbers (using all the mathematics that is natural here). Then can we conclude that P = NP over another field such as the algebraic numbers or even over Z₂? (Answer: Yes and essentially yes.)

I am particularly interested in such transfer results and problems that appear in the interface between the discrete and the continuous.

Back

Publications (selected)

Generalized Algebraic Structures: A Model Theoretical Approach,
Ph.D. Thesis, MIT, (1968)

Towards a Mathematical Theory of Inductive Inference,
Information and Control, 125-155, (June 1975) (with M. Blum)

Differentially Closed Fields: A Model Theoretic Tour,
Contributions to Algebra: A Collection of Papers Dedicated to Ellis Kolchin,
(ed. Bass/Cassidy Kovacic), Academic Press, Inc., (Fall 1977)
xx
A Simple Secure Pseudo-Random Number Generator,
SIAM Journal of Computing, Vol.15, No.2, 364-383, (May 1986)
(with M. Blum and M. Shub)

Evaluating Rational Functions : Infinite Precision is Finite Cost and Tractable on Average
SIAM Journal of Computing, Vol. 15, No.2, 384-398, (May 1986) (with M. Shub)

Towards an Asymptotic Analysis of Karmarkar’s Algorithm,
Information Processing Letters, Vol. 23, No.4, 189-194, (Nov 1986)

A New Simple Homotopy Algorithm for Linear Programming I,
Journal of Complexity, Vol.4, No.2, 124-136, (June 1988)

On a Theory of Computation Over the Real Numbers; NP Completeness,
Recursive Functions and Universal Machines, Bulletin of the AMS,
Vol. 21, No.1, 1-46, (July 1989) (with M. Shub and S. Smale)

Lectures on Theory of Computation and Complexity Over the Reals (or an Arbitrary Ring),
Lectures in the Sciences of Complexity, Addison Wesley, 1-47, (1990)

The Gödel Incompleteness Theorem and Decidability Over a Ring,
Proceedings of the Smalefest, (1990) (with S. Smale)

A Theory of Computation and Complexity Over the Real Numbers,
Proceedings of the ICM-90, Springer-Verlag, (1991)

Algebraic Settings for the Problem “P=NP?”,
The Mathematics of Numerical Analysis, Volume 42, Lectures in Applied Mathematics,
pp. 125-144. AMS (1996) (with F. Cucker, M. Shub and S. Smale)

Complexity and Real Computation,
Springer-Verlag (1997) (with F. Cucker, M. Shub and S. Smale)

Julia, A Life in Mathematics, reviewed by Lenore Blum, the American Mathematical Monthly,
Vol. 105, No.10, pp. 964-972 (December 1998)

Back

Biography

After attending public schools in New York City and junior and high school in Caracas, Venezuela, Lenore Blum enrolled in the Architecture Department at Carnegie Institute of Technology in Pittsburgh at the age of 16. During her sophomore year she changed her major to mathematics (her first love), taking electives in sculpture and design. Encouraged by Alan Perlis, Blum enrolled in his experimental computing class. Programs were written in TASS (Perlis' assembly language) on stacks of punch cards and run overnight on an IBM 650 (located in the basement of GSIA, the Graduate School of Industrial Administration). Unbeknownst to the students, Perlis' assignments often contained yet unsolved problems. The year was 1960. In 1961, she moved to Cambridge, Massachusetts and immersed herself in mathematics.

Blum received her Ph.D. in mathematics from M.I.T. in 1968 (the famous year Princeton University first allowed women to enter their graduate program ---and other amazing revolutionaryxeventsx!!!). She then went to UC Berkeley as a Postdoctoral Fellow and Lecturer in Mathematics. In 1973 she joined the faculty of Mills College where in 1974 she founded the Mathematics and Computer Science Department (serving as its Head or co-Head for 13 years). In 1979 she was awarded the first Letts-Villard Chair at Mills.

An NSF Career Advancement Award in 1983 enabled Blum to embark on a longtime scientific collaboration with Mike Shub. She spent part of the next two years in New York as Visiting Professor at the CUNY Graduate Center and returned to New York in 1987 as Visiting Scientist at the IBM TJ Watson Research Center.

In 1988 Blum joined the Theory Group of the newly formed International Computer Science Institute (ICSI) in Berkeley. From 1992 to 1996 she also served as Deputy Director of the Mathematical Sciences Research Institute (MSRI) in Berkeley.

Straddling the historic handover of Hong Kong from Britain to China on July 1, 1997, Blum spent two years, 1996-1998, at the City University of Hong Kong (CityU) as Visiting Professor of Mathematics and Computer Science. Here she completed her book, Complexity and Real Computation, with colleagues and co-authors Felipe Cucker, Mike Shub and Steve Smale and also helped revise the CityU undergraduate mathematics program.

In the fall of 1999, Blum joined the faculty of the School of Computer Science at Carnegie Mellon University where she is Distinguished Career Professor of Computer Science. Along with Guy Blelloch, she is co-Director on the NSF-ITRxALADDIN Center for ALgorithm ADaptation Dissemination and INtegration. The primary goal of ALADDIN is to improve the process of incorporating powerful algorithms into application domains.

-------------------------------------------

Lenore Blum’s research, from her early work in model theory and differential fields (logic and algebra) to her more recent work with Shub and Smale in developing a theory of computation and complexity over the real numbers (mathematics and computer science), has focused on merging seemingly unrelated areas. In 1990 she reported on this latter work at the International Congress of Mathematicians in Kyoto. She has also given invited talks at international conferences in the US, Europe, China, Southeast Asia, the former Soviet Union, Latin America and Africa.

Blum is well known for her work in increasing the participation of girls and women in mathematics and scientific fields. She was instrumental in founding the Association for Women in Mathematics (serving as its President from 1975 to 1978), the Math/Science Network and its Expanding Your Horizons conferences for high school girls (serving as co-Director from 1975 to 1981) and served as co-PI for the Mills Summer Mathematics Institute for undergraduate women. At Carnegie Mellon she has been faculty advisor to the Women@SCS and a member of the President's Diversity Advisory Council.

Blum has also been committed to increasing public understanding of mathematics, prominent examples of which have been MSRI’s Fermat Fest and “Conversations” between mathematics teachers and researchers. For the Y2K meeting of the American Association for the Advancement of Science (AAAS) in Washington, DC, she organized a day long symposium on The Reasonable Effectiveness of Mathematics (Part I. Mathematics in Hollywood, Industry and Daily Life, Part II. Complexity and Computation: Paradigms for the 21st Century).

Throughout her career, Blum has been an active member of the professional societies. She served on the Council and as Vice President of the American Mathematical Society (1990-1992). After representing the AMS at the Pan African Congress of Mathematicians in Nairobi in the summer of 1991, she became committed to building links between the American and African mathematics communities. She served as Chair of the AAAS Mathematics Section for the years 1998-1999.

In 1979 Blum was elected Fellow of the AAAS. In June 1999, on the 25th anniversary of the founding the Department of Mathematics and Computer Science at Mills College, she was awarded Doctor of Laws, honoris causa.

Biographies of Lenore Blum can be found in Notable Women of Mathematics, Women in Mathematics: The Addition of Difference, the Agnes Scott web site, the The MacTutor History of Mathematics archive, the delightful book Women and Numbers for grade school girls, and the new Career Ideas for kids who like math. For more information about Lenore and her family see Pittsburgh Post-Gazette article, Dad, mom join son to form a potent computer science team at CMU.

Back